/* eslint-disable no-param-reassign */
/**
 * Merge the 2 sorted array into one array
 * @param A the input unsorted array
 * @param array1Start the first array start index
 * @param array1End the first array last index
 * @param array2End the second array start index
 */
export function merge(A: number[], array1Start: number, array1End: number, array2End: number): void {
	const array1Length = array1End - array1Start + 1
	const array2Length = array2End - array1End
	const array1 = new Array<number>(array1Length + 1)
	const array2 = new Array<number>(array2Length + 1)
	for (let i = 0; i < array1Length; i += 1) {
		array1[i] = A[array1Start + i]
	}
	for (let i = 0; i < array2Length; i += 1) {
		array2[i] = A[array1End + i + 1]
	}
	// set the end flag
	array1[array1Length] = Number.MAX_VALUE
	array2[array2Length] = Number.MAX_VALUE

	// merge 2 sorted arrays into one
	let i = 0
	let j = 0
	for (let k = array1Start; k <= array2End; k += 1) {
		if (array1[i] <= array2[j]) {
			A[k] = array1[i]
			i += 1
		} else {
			A[k] = array2[j]
			j += 1
		}
	}
}

export function mergeSort(A: number[], p: number, r: number): number[] {
	if (p < r) {
		const q = Math.floor((p + r) / 2)
		mergeSort(A, p, q)
		mergeSort(A, q + 1, r)
		merge(A, p, q, r)
	}

	return A
}

console.log(mergeSort([3, 2, 1, 6, 5, 4], 0, 5))
